/*
 * 10.1.cpp 1163_poj
 *
 *  Created on: 2012-5-16
 *      Author: jawinton
 */


#include <cstdio>
#include <algorithm>

using namespace std;

#define MAX 101

int triangle[MAX][MAX];
int result[MAX][MAX];
int n;

int maxSum(int i, int j) {
	if (i == n-1) result[i][j] = triangle[i][j];
	if (result[i][j] != -1) return result[i][j];
	result[i][j] = max(triangle[i][j] + maxSum(i+1, j), triangle[i][j] + maxSum(i+1, j+1));
	return result[i][j];
}

int main (void) {
	scanf("%d", &n);
	for (int i=0; i<n; i++) {
		for (int j=0; j<=i; j++) {
			scanf("%d", &triangle[i][j]);
			result[i][j] = -1;
		}
	}
	printf("%d\n", maxSum(0, 0));
	int j = 0;
	printf("%d ", triangle[0][0]);
	for (int i=0; i<n-1; i++) {
		result[i+1][j] > result[i+1][j+1] ? : j=j+1;
		printf("%d ", triangle[i+1][j]);
	}
	return 0;
}
